'''
    两数之和：
'''

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        left,right = 0,len(numbers) - 1
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                return [left + 1,right + 1]
            elif sum < target:
                left += 1
            else:
                right -= 1
        return [-1,-1]
    
    def twoSum2(self, numbers: List[int], target: int) -> List[int]:

        '''
            哈希表，对应python的字典
        '''
        record = {}
        for i in range(len(numbers)):
            diff = target - numbers[i]
            if diff in record.keys():
                return [record.get(diff) + 1,i + 1]
            else:
                record[numbers[i]] = i
        return [-1,-1]
    
    def twoSum3(self, numbers: List[int], target: int) -> List[int]:

        for i in range(len(numbers)):
            index= self.binary_search(numbers,target - numbers[i])
            if index != -1:
                if numbers[index]< numbers[i]:
                    return [index ,i]
                else:
                    return [i,index]
        return [-1,-1]

    

    def binary_search(self,nums,x):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == x:
                return mid
            elif nums[mid] < x:
                right = mid - 1 
            else:
                left = mid + 1
        return -1
    

